<?php
//无序数组排序后的最大相邻差

class MaxSortedDistance {

    /**
     * 计数排序法
     * @param array $arr
     * @return int
     */
    public function countSort(array $arr) {
        //1. 求出原数组的max和min, 则区间长度k=max-min+1, 偏移量d=min
        //2. 创建一个长度为k的新数组
        //3. 遍历原数组, 如果元素值为n, 则将新数组的 [n-min] 位置的值+1. 结束后, 新数组的一部分元素的值>=1, 一部分的值认为0
        //4. 遍历新数组, 统计其中最大连续出现0值的次数+1, 即为相邻元素的最大差值.

        //NOTE: 致命的缺点! 当 max-min 的值很大时, 就需要创建很大的数组!

        //1. 获取最大最小值
        $max = $arr[0];
        $min = $arr[0];
        for ($i = 1, $n = count($arr); $i < $n; $i++) {
            if ($arr[$i] > $max) {
                $max = $arr[$i];
            }
            if ($arr[$i] < $min) {
                $min = $arr[$i];
            }
        }

        //echo 'max=' . $max . ', min=' . $min . PHP_EOL;
        if ($max == $min) {
            return 0;
        }

        //2. 新数组
        $k = $max - $min;
        $arr2 = array_fill(0, $k, 0);

        //3. 遍历原数组, 更新新数组
        for ($i = 0, $n = count($arr); $i < $n; $i++) {
            $ix = $arr[$i] - $min;
            $arr2[$ix] = $arr2[$ix] + 1;
        }

        //4. 遍历新数组, 统计其中最大连续出现0值的次数
        $maxDistance = 0;
        $distance = 0;
        for ($i = 0; $i < $k; $i++) {
            if ($arr2[$i] == 0) {
                $distance++;
            } else {
                if ($distance > $maxDistance) {
                    $maxDistance = $distance;
                }
                $distance = 0;
            }
        }
        if ($maxDistance === 0) {
            $maxDistance = $distance;
        }

        return $maxDistance + 1;
    }

    /**
     * 桶排序
     * @param array $arr
     * @return int
     */
    public function bucketSort(array $arr) {
        //1. 利用桶排序的思想, 根据原数组的长度n, 创建出n个桶, 每一个桶代表一个区间范围. 日中第一个桶从原数组的最小值min开始, 区间跨度是 (max-min)/(n-1);
        //2. 遍历原数组, 把原数组的每一个元素插入到对应的桶中, 记录每一桶的最大和最小值
        //3. 遍历所有的桶, 统计出每一个桶的最大值, 和这个桶右侧非空桶的最小值的差, 数值最大的差即为原数组排序后的相邻最大差值

        //1. 获取最大最小值
        $max = $arr[0];
        $min = $arr[0];
        $len = count($arr);
        for ($i = 1; $i < $len; $i++) {
            if ($arr[$i] > $max) {
                $max = $arr[$i];
            }
            if ($arr[$i] < $min) {
                $min = $arr[$i];
            }
        }

        if ($max === $min) {
            return 0;
        }

        //2. 初始化桶
        $d = $max - $min;
        //echo 'max=' . $max . ', min=' . $min . ', 偏移量: d=' . $d . PHP_EOL;
        $buckets = [];
        for ($i = 0; $i < $len; $i++) {
            $buckets[$i] = ['max' => null, 'min' => null];
        }

        //3. 遍历原数组, 确定每个桶的最大值和最小值
        for ($i = 0; $i < $len; $i++) {
            //确定数组元素归属的下标
            $ix = floor(($arr[$i] - $min) * ($len - 1) / $d);// floor, ceil
            if ($buckets[$ix]['min'] === null || $buckets[$ix]['min'] > $arr[$i]) {
                $buckets[$ix]['min'] = $arr[$i];
            }
            if ($buckets[$ix]['max'] === null || $buckets[$ix]['max'] < $arr[$i]) {
                $buckets[$ix]['max'] = $arr[$i];
            }
        }

        //4. 遍历桶, 找到最大差值
        $leftMax = $buckets[0]['max'];//第一个桶肯定不会为空
        $maxDistance = 0;
        for ($i = 1; $i < $len; $i++) {
            if ($buckets[$i]['min'] === null) {
                //echo $i . ' 为空, 忽略' . PHP_EOL;
                continue;
            }
            if ($buckets[$i]['min'] - $leftMax > $maxDistance) {
                $maxDistance = $buckets[$i]['min'] - $leftMax;
            }
            $leftMax = $buckets[$i]['max'];
        }

        return $maxDistance;
    }

}

//$arr = [2, 6, 3, 4, 5, 10, 9];
$arr = [];
for ($i = 0; $i < 1000; $i++) {
    $arr[] = rand(100, 100000);
}
$m = new MaxSortedDistance();

echo '计数排序: ';
$time1 = microtime(true);
$maxDistance = $m->countSort($arr);
$time2 = microtime(true);
echo '结果: ' . $maxDistance . ', 用时: ' . (round($time2 - $time1, 6) * 1000) . 'ms' . PHP_EOL . PHP_EOL;

echo '桶排序: ';
$time1 = microtime(true);
$maxDistance = $m->bucketSort($arr);
$time2 = microtime(true);
echo '结果: ' . $maxDistance . ', 用时: ' . (round($time2 - $time1, 6) * 1000) . 'ms' . PHP_EOL;